package P454_四数相加;

import java.util.HashMap;
import java.util.Map;

//关键词: 哈希
public class Solution {
    //方法 A + B = -(C + D)
    //做两个HashMap  一个KEY装A+B的全部值，VALUE装这个值得碰撞数,另一个是C+D的
    //超时！！！

    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer,Integer> abMap = new HashMap<>(A.length + B.length);
        Map<Integer,Integer> cdMap = new HashMap<>(C.length + D.length);
        for(int a : A){
            for(int b : B){
                abMap.put(a + b, abMap.getOrDefault(a+b,0) + 1);
            }
        }
        for(int c : C){
            for(int d : D){
                cdMap.put(c + d, cdMap.getOrDefault(c+d,0) + 1);
            }
        }
        int count = 0;
        for(Map.Entry<Integer,Integer> abEntry : abMap.entrySet()){
            for(Map.Entry<Integer,Integer> cdEntry : cdMap.entrySet()){
                if(abEntry.getKey() + cdEntry.getKey() == 0){
                    count += abEntry.getValue() * cdEntry.getValue();
                }
            }
        }
        return count;

    }

    //简化版本
    //总结：看到形如：A+B....+N=0的式子，要转换为(A+...T)=-((T+1)...+N)再计算，这个T的分割点一般是一半，特殊情况下需要自行判断。定T是解题的关键
    public int fourSumCount2(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer,Integer> abMap = new HashMap<>(A.length + B.length);
        for(int a : A){
            for(int b : B){
                abMap.put(a + b, abMap.getOrDefault(a+b,0) + 1);
            }
        }
        int count = 0;
        for(int c : C){
            for(int d : D){
                if(abMap.containsKey(-(c+d))){
                    count +=abMap.get(-(c+d));
                }
            }
        }

        return count;

    }
}
